﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include <assert.h>
#include <math.h>

using namespace std;	

template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data = T())
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _bf(0)
	{}

	AVLTreeNode<T>* _pLeft;
	AVLTreeNode<T>* _pRight;
	AVLTreeNode<T>* _pParent;
	T _data;
	int _bf;   // 节点的平衡因子
};


// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:
	//查找节点
	bool Find(const T& date)
	{
		Node* cur = _pRoot;
		while (cur)
		{
			if (date < cur->_data)
			{
				cur = cur->_pLeft;
			}
			else if (date > cur->_data)
			{
				cur = cur->_pRight;

			}
			else
			{
				return true;
			}

		}
		return false;
	}


	AVLTree()
		: _pRoot(nullptr)
	{}

	// 在AVL树中插入值为data的节点
	bool Insert(const T& data)
	{
		// 空树 → 新节点直接为根
		Node* newnode = new Node(data);
		if (_pRoot == nullptr)
		{
			_pRoot = newnode;
			return true;
		}
		// 1. 正常 BST 插入
		Node* parent = nullptr;
		Node* cur = _pRoot;
		// 找到插入位置
		while (cur)
		{
			parent = cur;
			if ( data > cur->_data)
			{
				cur = cur->_pRight;
			}
			else if (data < cur->_data)
			{
				cur = cur->_pLeft;
			}
			else
			{
				return false;// 不允许重复
			}
		}

		// 挂接到父节点下
		cur = newnode;
		if (cur->_data > parent->_data)
		{
			parent->_pRight = cur;
			cur->_pParent = parent;
		}
		else
		{
			parent->_pLeft = cur;
			cur->_pParent = parent;
		}

		
		//更新平衡因子
		while (parent)
		{
			// 新节点在左边 → 左子树变高 → bf -1
			// 新节点在右边 → 右子树变高 → bf +1
			if (cur == parent->_pLeft)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;

			}
			// 如果 bf == 0，高度没变，结束
			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)// 如果 |bf| == 1，高度改变但不失衡，继续向上更新
			{
				cur = parent;
				parent = parent->_pParent;
			}
			else if (parent->_bf == -2 ||parent->_bf==2)// |bf| == 2 → 失衡，需要旋转
			{

				if (parent->_bf == -2 && cur->_bf == -1)// 右单旋
				{
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == 1)// 左单旋
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1 )//左右双旋
				{
					//
					RotateLR(parent);

				}
				else if (parent->_bf == 2 && cur->_bf == -1)//右左双旋
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);

				}
				break;// 旋转后高度恢复平衡，不需要继续更新
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

	
	// AVL树的验证
	bool IsAVLTree()
	{
		return _IsAVLTree(_pRoot);
	}
	// 节点个数
	size_t Size()
	{
		return _size(_pRoot);

	}

	// 树高
	size_t Height()
	{
		return _Height(_pRoot);
	}
private:
	// 根据AVL树的概念验证pRoot是否为有效的AVL树
	
	// 统计节点数量
	size_t _size(Node* pRoot)
	{
		if (pRoot == nullptr)
		{
			return 0;
		}
		return 1 + _size(pRoot->_pLeft) + _size(pRoot->_pRight);
	}
	// 判断 AVL 性
	bool _IsAVLTree(Node* pRoot)
	{
		if (pRoot == nullptr)
		{
			return true;
		}

		int left_hight = _Height(pRoot->_pLeft);
		int right_hight = _Height(pRoot->_pRight);

		int beff = right_hight - left_hight;// 正式平衡因子
		if (abs(beff) >= 2)
		{
			cout << "高度差异常" << endl;
			return false;
		}
		if (beff != pRoot->_bf)
		{
			cout << "平衡因子异常" << endl;
			return false;
		}
		return _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
	}

	size_t _Height(Node* pRoot)
	{
		if (pRoot == nullptr)
		{
			return 0;
		}
		int left_hight = _Height(pRoot->_pLeft);
		int right_hight = _Height(pRoot->_pRight);
		return  left_hight > right_hight ? left_hight + 1 : right_hight + 1;
	}

	// 右单旋
	void RotateR(Node* pParent)
	{
		Node* father = pParent;
		Node* sonL = father->_pLeft;
		// 1. 先把 sonL 挪到 father 的位置
		sonL->_pParent = father->_pParent;
		if (father->_pParent)
		{
			if (father == father->_pParent->_pLeft)
			{
				
				father->_pParent->_pLeft = sonL;
			}
			else
			{
				father->_pParent->_pRight = sonL;

			}
		}
		else
		{
			_pRoot = sonL;
		}

		// 2. 调整 father
		father->_pParent = sonL;
		father->_pLeft = sonL->_pRight;

		if (sonL->_pRight)
			sonL->_pRight->_pParent = father;

		sonL->_pRight = father;
		sonL->_bf = father->_bf = 0;


	}
	// 左单旋
	void RotateL(Node* pParent)
	{
		Node* father = pParent;
		Node* sonR = father->_pRight;

		sonR->_pParent = father->_pParent;
		if (father->_pParent)
		{
			if (father == father->_pParent->_pLeft)
			{
				father->_pParent->_pLeft = sonR;
			}
			else
			{
				father->_pParent->_pRight = sonR;

			}
		}
		else
		{
			_pRoot = sonR;
		}

		father->_pParent = sonR;
		father->_pRight= sonR->_pLeft;

		if (sonR->_pLeft)
			sonR->_pLeft->_pParent = father;

		sonR->_pLeft = father;

		sonR->_bf = father->_bf = 0;

	}
	// 右左双旋
	void RotateRL(Node* pParent)
	{

		Node* parent = pParent;
		Node* sonR = parent->_pRight;
		Node* sonRL = sonR->_pLeft;

		int sonRLbf = sonRL->_bf;
		RotateR(sonR);
		RotateL(parent);

		if (sonRLbf == -1)
		{
			parent->_bf = 0;
			sonRL->_bf = 0;
			sonR->_bf = 1;

		}
		else if (sonRLbf == 1)
		{
			parent->_bf = -1;
			sonRL->_bf = 0;
			sonR->_bf = 0;
		}
		else if (sonRLbf == 0)
		{
			parent->_bf = 0;
			sonRL->_bf = 0;
			sonR->_bf = 0;
		}
		else
		{
			assert(false);
		}


	}
	// 左右双旋
	void RotateLR(Node* pParent)
	{

		
		Node* sonL = pParent->_pLeft;
		Node* sonLR = sonL->_pRight;

		int sonLRbf = sonLR->_bf;
		RotateL(sonL);
		RotateR(pParent);
		if (sonLRbf == -1)
		{
			sonLR->_bf = 0;
			sonL->_bf = 0;
			pParent->_bf = 1;
		}
		else if(sonLRbf == 1)
		{
			sonLR->_bf = 0;
			sonL->_bf = -1;
			pParent->_bf = 0;
		}
		else if(sonLRbf == 0)
		{
			sonLR->_bf = 0;
			sonL->_bf = 0;
			pParent->_bf = 0;
			
		}
		else
		{
			assert(false);

		}
	}

private:
	Node* _pRoot;
};